package zhoujian.oj.leetcode;

import java.util.Hashtable;

/*
 * Given a string S and a string T, find the minimum window in S 
 * which will contain all the characters in T in complexity O(n).
 * 
 * For example,
 * 	S = "ADOBECODEBANC"
 * 	T = "ABC"
 * 	Minimum window is "BANC".
 * 
 * Note:
 * 	If there is no such window in S that covers all characters in T, 
 * 	return the emtpy string "".
 * 
 * 	If there are multiple such windows, you are guaranteed that 
 * 	there will always be only one unique minimum window in S.
 */
public class MinWindow {

	public String minWindow(String S, String T) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
		Hashtable<Character, Integer> goal = new Hashtable<Character, Integer>();  
        Hashtable<Character, Integer> process = new Hashtable<Character, Integer>();  
        int lenS = S.length();  
        int lenT = T.length();  
        int total = lenT;  
        int counter = 0;  
        
        for (int i = 0; i < lenT; i++) {
        	char cur = T.charAt(i);
        	process.put(cur, 0);
        	if (!goal.containsKey(cur)) 
        		goal.put(cur, 1);
        	else
        		goal.put(cur, goal.get(cur) + 1);
        }
        
        int start = 0;
        int end = 0;
        int minWin = lenS + 1;
        int minStart = 0;
        int minEnd = 0;
        while (end < lenS) {
        	char sCh = S.charAt(start);
          	char eCh = S.charAt(end);
        	if (!goal.containsKey(eCh)) {
        		end++;
        		continue;
        	}
        	if (process.get(eCh) < goal.get(eCh)) {
        		counter++;
        	}
        	process.put(eCh, process.get(eCh) + 1);
        	if (counter == total) {
        		while (!process.containsKey(sCh) || process.get(sCh) > goal.get(sCh)) {
        			if (process.containsKey(sCh)) {
        				process.put(sCh, process.get(sCh) - 1);        			
        			} 
        			start++;
        			sCh = S.charAt(start);
        		}
        		int len = end - start + 1;
        		if (len < minWin) {
        			minWin = len;
        			minStart = start;
        			minEnd = end;
        		}
        	}
        	end++;
        }
        
        return minWin <= lenS ? S.substring(minStart, minEnd + 1) : "";
    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MinWindow minWindow = new MinWindow();
		String S;
		String T;
		
		S = "ADOBECODEBANC";
		T = "ABC";
		assert minWindow.minWindow(S, T).equals("BANC");
		
		S = "BAAC";
		T = "ABC";
		assert minWindow.minWindow(S, T).equals("BAAC");

	}

}
